Kunerth's algorithm

Kunerth's algorithm is an algorithm for computing the modular square root of a given number. The algorithm does not require the factorization of the modulus, and relies on modular operations that is often easy when the given number is prime.

Algorithm

To find y from a given value

$B=y^{2}modN,$

it takes the following steps:

1. find the modular square root of $r\equiv \sqrt{\pm N}(\mathrm{mod}B)$. This step is quite easy, irrespectively of how big N when $B$ is a prime.
2. solve a quadratic equation associated with the modular square root of $w^2=A\cdot z^2+B\cdot z+C$. Most of Kunerth's examples in his original paper solve this equation by having C be a integer square and thus setting z to zero.

   Expand out the following equation to obtain the quadratic

   $((B\cdot z+r{)}^2\pm N)/B=w^2.$

   One can always make sure that the quadratic can be solved by adjusting the modulus N in the above equation. Thus

   $((B\cdot z+r{)}^2+(B\cdot F+N))/B=w^2$

   will ensure a quadratic of $A\cdot z^2+D\cdot z+C+F$.

   One can then adjust F to make sure that $C+F$ is a square. For large moduli, such as $\sqrt{67}mod67F+RSA260$, can have their square roots computed quickly via this method.

   The parameters of the polynomial expansion are quite flexible, in that $((67z+r{)}^2+X\cdot RSA260)/(67y)$ can be done, for instance. It is quite easy to choose X and Y such that $(r^2+X\cdot RSA260)/(67y)$ is a square. The modular square root of $\sqrt{67y}modRSA260$ can be taken this way.

3. Having solved the associated quadratic equation we now have the variables w and set v = r (if C in the quadratic is a natural square).
4. Solve for variables $\alpha$ and $\beta$ the following equation:

   $\alpha =w(v+w\beta ),$

5. Obtain a value for X via factorization of the following polynomial:

   ${\alpha }^2\cdot x^2+(2\alpha \beta -N)x+({\beta }^2-(y^{2}modN))$

   obtaining an answer like

   $(-37+9x)(1+25x)$

6. Obtain the modular square root by the equation. Remember to set X such that the term above is zero. Thus X would be 37/9 or -1/25.

   $y\equiv \alpha X+\beta (\mathrm{mod}N).$

Example

To obtain $\sqrt{41}mod856,$ first obtain $\sqrt{-856}\equiv 13(\mathrm{mod}41)$.

Then expand the polynomial:

$((41z+13{)}^2+856)/41=w^2$

into

$25+26z+41z^2$

Since, in this case the C term is a square, we take $w=5$ and compute $v=13$ (in general, $v=41\cdot z+13$).

Solve for $\alpha$ and $\beta$ the following equation

$\alpha ==w(v+w\beta )$

getting the solution $\alpha =15$ and $\beta =-2$. (There may be other pairs of solutions to this equation.)

Then factor the following polynomial:

${\alpha }^2{x}^2+(2\alpha \beta -856)x+({\beta }^2-41)$

obtaining

$(-37+9x)(1+25x)$

Then obtain the modular square root via

$15\cdot (37\cdot 9^{-1})+(-2)\equiv 345(\mathrm{mod}856).$

Verify that $345^2\equiv 41(\mathrm{mod}856).$

In the case that $\sqrt{-856}mod41$ has no answer, then $r\equiv \sqrt{-856}(\mathrm{mod}b\cdot 856+41)$ can be used instead.

See also

• Methods of computing square roots

References

• Adolf Kunerth, "Sitzungsberichte. Academie Der Wissenschaften" vol 75 ,II, 1877, pp. 7-58
• Adolf Kunerth, "Sitzungsberichte. Academie Der Wissenschaften" vol 82, II, 1880, pp. 342-375